package com.jwetherell.my;

public class Utils {

	/**
	 * 
	 * Properties of partitioning logic:
	 * 
	 * <br/>
	 * <br/>
	 * 
	 * 1. We don't maintain a pivot pointer (pointer which points to pivot
	 * position at any point of time) explicitly because after the partition,
	 * both left_pointer and right_pointer will point to pivot only
	 * 
	 * @return index of pivot element after partitioning
	 */
	public static int partition(int[] data, int low, int high) {

		int pivot = data[(low + high) / 2];

		/*
		 * (low < high) and not (low <= high) because after the partition, both
		 * left_pointer and right_pointer will be equal as they both will point
		 * to pivot only
		 */
		while (low < high) {

			/*
			 * Note that here data[i] < pivot and not '<='. Even though we are
			 * increasing i, it will never cross 'high' because along the way it
			 * will encounter pivot and will come out of the loop and thus there
			 * is no need to check whether i <= high in every iteration. So the
			 * max. value that i can have here is the pivot index.
			 * 
			 * The same logic applies to the second while loop also
			 */
			while (data[low] < pivot)
				low++;

			while (data[high] > pivot)
				high--;

			swap(data, low, high);
		}

		return low;
	}

	public static void swap(int[] data, int i, int j) {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	public static void print(int[] input) {
		for (int i : input) {
			System.out.print(i + " ");
		}
		System.out.print("\n");
	}

}
